class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False] * len(s) for _ in s]

        left, right = 0, 0
        for i in range(len(dp)-1, -1, -1):
            for j in range(i, len(dp)):
                if i == j:
                    dp[i][j] = True
                elif i == j - 1:
                    dp[i][j] = s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
                if dp[i][j] and right - left < j - i:
                    left, right = i, j
        return s[left:right+1]
        